package leetcode_1_20;

import java.util.*;

public class threeSum_15 {
    /**
     * 一个整数数组 nums ，判断是否存在三元组
     * 返回所有和为 0 且不重复的三元组。
     * 暴力三层for循环
     * 时间效率太低
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>> ans=new ArrayList<>();
         for(int i=0;i<nums.length;i++) {
             for (int t = i + 1; t < nums.length; t++) {
                 int OppositeNum=-(nums[i]+nums[t]);
                 //确定两个数字后，看剩下的是否存在符合条件的第三个数
                 for (int j = t + 1; j < nums.length; j++) {
                     if( nums[j] == OppositeNum ){
                         List<Integer>a=new ArrayList<>();
                         a.add(nums[i]);
                         a.add(nums[j]);
                         a.add(nums[t]);
                         ans.add(a);
                     }
                 }
             }
         }
         //不可以包含重复的三元组
         //进行处理
        for (int i=0;i<ans.size();i++){
            for (int t = i + 1; t < ans.size(); t++) {
                List list1=ans.get(i);
                List list2=ans.get(t);
                boolean result = list1.containsAll(list2) && list2.containsAll(list1)
                        && list1.size() == list2.size()
                        && list1.stream().mapToInt(x -> (int) x).sum()
                        ==list2.stream().mapToInt(x -> (int) x).sum();
                if(result){
                    ans.remove(t);  //ans的大小发生了变化
                    t--;
                }
            }
        }
        return ans;
    }

    /**
     * 可以预先给数组进行排序
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        int len=nums.length;
        List<List<Integer>> ans=new ArrayList<>();
        // 无法构成3元组
        if(len < 3) {
            return ans;
        }
        Arrays.sort(nums);         //从小到大排序

        int lastnums1=Integer.MIN_VALUE,
                lastnums2=Integer.MIN_VALUE;
        for(int i=0; nums[i] <= 0 && i < len -2; i++) {                                      //第一个数
            //nums[i] > 0 时，说明后边之和肯定都大于0
            if( lastnums1 != Integer.MIN_VALUE && nums[i] == lastnums1)             //数字与上一个数字相同直接跳过
                continue;
            for (int t = i + 1; t < len-1; t++) {                    //第二个数
                if( lastnums2 != Integer.MIN_VALUE && nums[t] == lastnums2)             //数字与上一个数字相同直接跳过
                    continue;
                int b=nums[i];
                int c=nums[t];
                //确定两个数字后，看剩下的是否存在符合条件的第三个数
                for (int j = t + 1; j < len; j++) {
                    int d=nums[j];
                    if( d == -(b+c) ){
                        ans.add(Arrays.asList(b,c,d));
                        break;                  //匹配到直接退出
                    }
                }
                lastnums2=nums[t];
            }
                lastnums1=nums[i];
                lastnums2=Integer.MIN_VALUE;
        }
        return ans;
    }


    /**
     * 优化第二个方案
     * 定义三个指针，
     * 第一个指针指向目前判定元素
     * 其余两个指针分别从左右与第一个元素匹配
     * 保证遍历数组中的每一个结果
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum3(int[] nums) {
        //定义一个结果集
        List<List<Integer>> res = new ArrayList<>();
        //数组的长度
        int len = nums.length;
        //当前数组的长度为空，或者长度小于3时，直接退出
        if (nums == null || len < 3) {
            return res;
        }
        //将数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for (int i = 0; i < len; i++) {
            //如果遍历的起始元素大于0，就直接退出
            //原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
            if (nums[i] > 0) {
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1;
            int r = len - 1;
            //当 l 不等于 r时就继续遍历
            while (l < r) {
                //将三数进行相加
                int sum = nums[i] + nums[l] + nums[r];
                //如果等于0，将结果对应的索引位置的值加入结果集中
                if (sum == 0) {
                    // 将三数的结果集加入到结果集中
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                    //如果重复，直接跳过。
                    //去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    //将 左指针右移，将右指针左移。
                    l++;
                    r--;
                    //如果结果小于0，将左指针右移
                } else if (sum < 0) {
                    l++;
                    //如果结果大于0，将右指针左移
                } else if (sum > 0) {
                    r--;
                }
            }
        }
        return res;
    }
}
